package com.lw.leetcode.other.b;

/**
 * create by idea
 * other
 * 390. 消除游戏
 *
 * @author lmx
 * @version 1.0
 * @date 2022/1/2 18:15
 */
public class LastRemaining {


    public static void main(String[] args) {
        LastRemaining test = new LastRemaining();

        // 6
//        int n = 9;

        // 7512
//        int n = 15623;

        // 6124926
        int n = 21569852;

        int i = test.lastRemaining(n);
        System.out.println(i);

    }

    public int lastRemaining(int n) {
        return find(n, 1, n, 1, true);
    }

    private int find(int count, int st, int end, int step, boolean flag) {
        if (count == 1) {
            return st;
        }
        count >>= 1;
        if (flag) {
            st = st + step;
            if ((((end - st) / step + 1) & 1) == 0) {
                end = end - step;
            }
            return find(count, st, end, step << 1, false);
        } else {
            end = end - step;
            if ((((end - st) / step + 1) & 1) == 0) {
                st = st + step;
            }
            return find(count, st, end, step << 1, true);
        }
    }
}
